package com.cjl.demo;

import static java.lang.Integer.min;

/**
 * <p>Description: </p>
 *给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * 示例：num1 = [1,3],num2=[2]
 * 返回中位数 2
 * num1=[1,3]
 * num2 = [2,4]
 * 返回中位数
 * @ uthor chenjinliang
 * @ date: 2020/6/1
 */
public class Zhongweishu {
    int getZhongweiShu(int[] nums1, int[] nums2, int k) {
        int size1 = nums1.length;
        int size2 = nums2.length;
        //
        int p1 = k/2 - 1;
        int p2 = k/2 - 1;
        int l1 = 0;
        int l2 = 0;

        while (l1 < size1 && l2 < size2) {
            if (k == 1){
                return nums1[l1]<nums2[l2]?nums1[l1]:nums2[l2];
            }

            p1 = min(l1 + k/2-1, size1 - 1);
            p2 = min(l2 + k/2-1, size2 - 1);

            if (nums1[p1] >= nums2[p2]) {
                k -= (p2 - l2 + 1);
                l2 = p2 + 1;
            }
            else {
                k -= (p1 - l1 + 1);
                l1 = p1 + 1;
            }
        }

        if (l1 < size1){
            return nums1[l1 + k - 1];
        }
        return nums2[l2 + k - 1];
    }

    public double Zhongweishu(int[] nums1, int[] nums2, int k){
        //计算总长度
        int totalLen = nums1.length + nums2.length;
        //判断总长度奇数偶数
        if (totalLen % 2 == 1) {
            //奇数，则为中间数
            return getZhongweiShu(nums1, nums2, totalLen/2 + 1);
        }else {
            return (getZhongweiShu(nums1, nums2, totalLen/2 + 1) + getZhongweiShu(nums1, nums2, totalLen/2)) / 2.0;
        }
    }
    public static void main(String[] args) {



    }

}
